ZK-SNARKs Homomorphic Hidings
要約 : E(x),E(y)がわかっていれば、E(x+y)がxとyが分からなくても計算できるような関数がある。x+y=7からx,yの組は無数に生成できるので、これだけでは別にありがたくない。
Homomorphic Hidings (HH）とは
HHである 関数E(x)は以下の条件を満たす。
1. 異なるインプットからは異なるアウトプットが得られる。x≠y => E(x)≠E(y)
2. E(x)が与えられている時に、E(x)からxを見つけるのは難しい。
3. E(x)とE(y）がわかっていれば、x,yがわからなくてもE(x+y)が計算できる。
HHがなぜZKに必要なのか？
AliceとBobの2人がいて、AliceがBobに対して$ x+y=7の答え($ 7のこと)を知っていることを証明したい。
Aliceが$ E(x)と$ E(y)をBobに送る。
Bobは$ E(x),E(y)から$ E(x+y)を計算する。
Bobは$ E(7)を計算する。これらにより、$ E(x+y) = E(7)が正しければAliceが$ x + yの結果である$ 7を知っていることが証明された。
素数を法とする剰余群
modを使う。mod nで表現される群を$ \mathbb{Z}_n = \{0,\cdots , n-1\}と表す。素数pを用いてmod pで考える時、$ \{1,\cdots ,p-1\}に含まれるの要素同士の掛け算の結果は$ \{1,\cdots ,p-1\}に含まれる。例えば$ 2\cdot4 = 1\ ({\rm mod}\ 7)である。
ここで、$ \mathbb Z_pから0を除いた$ \mathbb Z_p^* = \{1,\cdots ,p-1\}は以下のような性質を持つ。
1. $ \mathbb Z_p^*は巡回群である。つまり、$ \mathbb Z_p^*中のある要素$ g(原始根)を用いて、$ \mathbb Z_p^*内の要素はすべて$ g^a\ ( a\in\{0,\cdots ,p-2\})の形で表せる($ aと$ g^aが1対1対応)。0が含まれているのは、$ g^0=1だからである。 また、pが素数なので$ g^{p-1}=1が成り立つ(フェルマーの小定理)。
2. $ \mathbb Z_p^*に関してZK-SNARKs 離散対数問題は困難だと考えられている。つまり、pの数が大きくなると、$ \mathbb Z_p^*の中の要素hに対して$ \{0,\cdots ,p-2\}の中から、$ g^a = h ({\rm mod}\ p)を満たす$ aを探すのが困難となる。 3. $ a,b\in \{0,\cdots ,p-2\}について、フェルマーの小定理より$ g^a*g^b = g^{a+b} = g^{a+b ({\rm mod}\ p-1)}
$ E(x)=g^xはHomomorphic Hidingsである
$ E(x)=g^x\ {\rm mod}\ p ($ x\in \{0,\cdots ,p-2\}, $ gは$ \mathbb Z_p^*の原始根)とおいてみると、以下の議論からEはHomomorphic Hidingsであることが分かる。
$ \mathbb Z_p^*の1つ目の性質からわかるのは、$ xが異なれば$ E(x)は異なるということである。これはHHの1つ目の条件である。ここでxは$ \mathbb Z_{p-1}=\{0,\cdots ,p-2\}中の要素であり、はEがHHならば$ E(x)は異なるアウトプットを出力する。
$ \mathbb Z_p^*の2つ目の性質からわかるのは、$ E(x)= g^xの結果から$ xを逆算するのが難しいということである。これはHHの2つめの条件である。
$ \mathbb Z_p^* の3つ目の性質からわかるのは、$ E(x)*E(y) = g^x*g^y = g^{x+y({\rm mod}\ p-1)} = E(x+y)\quad ({\rm mod}\ p) が成り立ち、$ E(x)と$ E(y)から$ E(x+y)を計算できるということである。これはHHの3つめの条件である。